剑指offer 16——数值的整数次方

这道题可以利用二进制,就可以快速解决了。

原题

实现函数double Power(double base, int exponent),求base的exponent次方。不得使用库函数,同时不需要考虑大数问题。

示例 1:

1
2
输入: 2.00000, 10
输出: 1024.00000

示例 2:

1
2
输入: 2.10000, 3
输出: 9.26100

示例 3:

1
2
3
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/2^2 = 1/4 = 0.25

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数,其数值范围是 [−2^31, 2^31 − 1] 。

原题url:https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/

解题

这道题,如果你是用正常计算的话,提交之后会发现报超时,因此,肯定需要寻找捷径的。

因为不能使用库函数,而且上面普通方法也是会超时的,那么问题的关键就是在如何快速计算。

而如果想快的,最好的办法就是可以利用曾经计算的结果,避免重复计算。

我一开始的想法是,比如计算 2^6 ,从数学上来说,等同于计算 4^3。但如果要用这种逻辑的话,就必须要求传入参数 n 是 2^w(其中 w 是正整数),否则计算逻辑会比较复杂。因此放弃该方案。

二进制

重点依旧是放在利用曾经计算的结果,避免重复计算上,那么理想情况也就是计算 x^n 后,之后希望直接计算 x^2n,而x^2n = x^n * x^n = x^(n + n)

从上面的讨论可以看出,计算幂,可以转换成将指数进行合理的加法拆分。所谓合理,就是后一个是前一个的 2 倍,这样的话,就自然联想到要对指数从十进制转为二进制

1
2
7 = (111) = 1 * 2^2 + 1 * 2^1 + 1 * 2^0
9 = (1001) = 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 1 * 2^0

当然,上面是从大到小累加,实际计算时肯定是从小到大进行累加的。

说到二进制,肯定少不了位运算,那么计算每一位二进制上的值,有什么快速的方法呢?

有的,利用n & 1,求出最低位的值(0或者1),然后n >> 1,右移,相当于移除最低位,不停循环,也就能计算出二进制上每一位的值了。

接下来看看代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public double myPow(double x, int n) {
if (x == 0) {
return 0;
}

// 此处用long,是防止n是Integer.MIN_VALUE时,取反后直接就超过了Integer.MAX_VALUE
long b = n;
double res = 1.0;
if(b < 0) {
x = 1 / x;
b = -b;
}

while(b > 0) {
if ((b & 1) == 1) {
res *= x;
}
// 底数扩大
x *= x;
// 指数右移
b >>= 1;
}
return res;
}
}

提交OK。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题利用二进制,就可以快速解决了。

有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。

https://death00.github.io/

公众号:健程之道

健健 wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
如果您感觉文章不错,也愿意支持一下作者的话